package main

import (
	"fmt"
	"sort"
)

//0ms 100%,3.8MB 100%
func search(nums []int, target int) int {
	if len(nums) == 0 {
		return 0
	}
	l, r := 0, len(nums)-1
	for l < r {
		m := (l + r) / 2
		if nums[m] == target {
			break
		}
		if nums[m] > target {
			r = m - 1
		} else {
			l = m + 1
		}
	}
	m := (l + r) / 2
	if nums[m] != target {
		return 0
	}
	for i := m; i >= 0; i-- {
		if nums[i] != target {
			l = i + 1
			break
		}
	}
	for i := m; i < len(nums); i++ {
		if nums[i] != target {
			r = i - 1
			break
		}
	}
	return r - l + 1
}

//用时8ms  48%，3.8MB内存 57%
func search1(nums []int, target int) int {
	leftmost := sort.SearchInts(nums, target)
	if leftmost == len(nums) || nums[leftmost] != target {
		return 0
	}
	rightmost := sort.SearchInts(nums, target+1) - 1
	return rightmost - leftmost + 1
}

func main() {
	fmt.Println(search([]int{0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 8, 10, 10}, 4))
	fmt.Println(search1([]int{0, 0, 1, 1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 8, 10, 10}, 4))
}
